/* 基于堆实现的优先级队列 */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "my_dynomi_array.c"

typedef struct node {
    int* data;
    int priority; // 优先级
} node;

node* createNode(int x, int y, int priority) {
    node* n = (node*)malloc(sizeof(node));
    int* data = (int*)malloc(2 * sizeof(int));
    data[0] = x, data[1] = y;
    n->data = data;
    n->priority = priority;
    return n;
}

typedef struct MinHeap {
    DynamicArray* array;
} MinHeap;

/**
 * @brief 创建小顶堆
 * @param sizeOfType 数组元素类型大小
 * @return 小顶堆指针
*/
MinHeap* createMinHeap(size_t sizeOfType) {
    MinHeap* p = (MinHeap*)malloc(sizeof(MinHeap));
    p->array = createDynamicArray(sizeOfType);
    return p;
}

int ifEmptyInHeap(MinHeap *heap) {
    return heap->array->size == 0;
}

void up(MinHeap* heap, node* offerd) {
    int parent;
    int child = heap->array->size;
    // 检测容量
    ifExpand(heap->array);
    while (child > 0) {
        parent = floor((child - 1) / 2);
        node* parNode = getInDynamicArray(heap->array, parent);
        if (offerd->priority < parNode->priority) {
            swapToDynamicArray(heap->array, parent, child);
        } else {
            break;
        }
        child = parent;
    }
    replaceToDynamicArray(heap->array, child, offerd);
}

void down(MinHeap* heap, int parent) {
    int left = 2 * parent + 1;
    int right = left + 1;
    int max = parent;
    node* leftNode = getInDynamicArray(heap->array, left);
    node* rightNode = getInDynamicArray(heap->array, right);
    node* maxNode = getInDynamicArray(heap->array, max);
    if (left < heap->array->size && leftNode->priority < maxNode->priority) {
        max = left;
    }
    maxNode = getInDynamicArray(heap->array, max);
    if (right < heap->array->size && rightNode->priority < maxNode->priority) {
        max = right;
    }
    if (max != parent) {
        swapToDynamicArray(heap->array, max, parent);
        down(heap, max);
    }
}

/**
 * @brief 获取堆顶元素
 * @param heap 堆指针
*/
void* peek(MinHeap* heap) {
    return getInDynamicArray(heap->array, 0);
}

/**
 * @brief 删除指定索引元素
 * @param heap 堆指针
 * @param index 索引
*/
void* poll(MinHeap* heap ,int index) {
    // void* deleted = removeToDynamicArray(heap->array, index);
    // swapToDynamicArray(heap->array, index, heap->array->size - 1);
    // down(heap, index);
    // return deleted;
    void* deleted = getInDynamicArray(heap->array, index);
    swapToDynamicArray(heap->array, index, heap->array->size - 1);
    heap->array->size--;
    down(heap, index);
    return deleted;
}

/**
 * @brief 替换堆顶元素
 * @param heap 堆指针
*/
void replace(MinHeap* heap, void* replaced) {
    replaceToDynamicArray(heap->array, 0, replaced);
    down(heap, 0);
}

/**
 * @brief 向堆尾添加元素
 * @param heap 堆指针
 * @param offerd 要添加的元素
*/
void offer(MinHeap* heap, void* offerd) {
    up(heap, offerd);
    heap->array->size++;
}




typedef struct stack{
    int top;
    DynamicArray* array;
} stack;

/**
 * @brief 判断栈是否为空
 * @param s 传入栈指针
 * @return 1代表栈为空, 0代表栈不为空
*/
int ifEmpty(stack* s) {
    return s->array->size == 0;
}

/**
 * @brief 创建二维栈
 * @return 栈指针 
*/
stack* createStack() {
    stack* s = (stack*)malloc(sizeof(stack));
    s->array = createDynamicArray(sizeof(int*));
    s->top = -1;
    return s;
}

/**
 * @brief 入栈
 * @param s 栈指针
*/
void appendToStack(stack* s, int x, int y) {
    s->top++;
    int* arr = calloc(2, sizeof(int));
    arr[0] = x, arr[1] = y;
    appendToDynamicArray(s->array, arr);
}

/**
 * @brief 出栈
 * @param s 栈指针
*/
int* popToStack(stack* s) {
    int* pop = removeToDynamicArray(s->array, s->top);
    s->top--;
    return pop;
}

/**
 * @brief 获取栈顶元素
 * @param s 栈指针
*/
int* getTopInStack(stack* s) {
    return getInDynamicArray(s->array, s->array->size - 1);
}

// void main() {
//     MinHeap* p = createMinHeap(sizeof(node*));
//     node* node1 = createNode(10, 15, 1);
//     node* node2 = createNode(10, 15, 2);
//     node* node3 = createNode(10, 15, 6);
//     node* node4 = createNode(10, 15, 8);
//     node* node5 = createNode(10, 15, 10);
//     node* node6 = createNode(10, 15, 16);
//     node* node7 = createNode(10, 15, 20);
//     node* node8 = createNode(10, 15, 15);
//     node* node9 = createNode(10, 15, 30);
//     node* node10 = createNode(10, 15, 40);
//     node* node11 = createNode(10, 15, 56);
//     node* node12 = createNode(10, 15, 96);
//     node* node13 = createNode(10, 15, 26);
//     node* node14 = createNode(10, 15, 36);
//     node* node15 = createNode(10, 15, 56);
//     node* node16 = createNode(10, 15, 46);
//     node* node17 = createNode(10, 15, 66);
//     offer(p, node1);
//     offer(p, node2);
//     offer(p, node3);
//     offer(p, node4);
//     offer(p, node5);
//     offer(p, node6);
//     offer(p, node7);
//     offer(p, node8);
//     offer(p, node9);
//     offer(p, node10);
//     offer(p, node11); 
//     node* z = poll(p, 0);
//     printf("zz:%d\n", z->priority);
// }